#include "GraphFunctions.hpp"
#include "GraphDatabase.hpp"
#include "GraphExploration.hpp"
#include "VertexSorter.hpp"
#include "GraphPredicates.hpp"
#include "FrequentSubgraph.hpp"
#include <math.h>
#include <algorithm>
#include <fstream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/clustering_coefficient.hpp>

#include <boost/graph/johnson_all_pairs_shortest.hpp>
#include <boost/unordered_map.hpp>
#include <boost/graph/isomorphism.hpp>
#include "ullman.hpp"

#include <boost/graph/iteration_macros.hpp>

using namespace std;
using namespace boost;
using namespace TopologicalLearner;


EditOpDist GraphFunctions::GetDistribution(const vector< std::pair<Graph, VertexMappings > >& C,
                                           const GraphDatabase& D, int iIndex, const Graph& G, int iExcludeGraph, bool bUnique)
{

    const Graph* pUnion = &G;

    vector<Graph> kVec;

    if( bUnique )
        for(unsigned int i=0; i < C.size(); i++)
            kVec.push_back(C[i].first);


    const vector<Graph>& m_Graphs = D.GetGraphVector();

    const Graph& GP = G;

    int iTotalGraphsExamined = 0;

    map< EditOp, int > kSum;


    for(unsigned int i=0; i < m_Graphs.size(); i++)
    {
        // If it is non unique, we perform the ullman inside the GraphExploration class instead
        //if( IsSubgraphContained(GP, m_Graphs[i]) && i != (unsigned int)iExcludeGraph )



        if( i != 9999999) //(unsigned int)iExcludeGraph )
        {
            GraphExploration GE(m_Graphs[i], GP, bUnique);
            GraphExploration::EditOpIterator it(GE);


            // cout << "isDoneVertex" << it.isDoneVertex()  << ", isDoneEdge: " << it.isDoneEdge()  << "unique: " << bUnique << endl;

            // When the graph exploration object is created, it performs a subgraph test
            // and if isDoneVertex and isDoneEdge is not true, then it means that the subgraph was contained in the larger graph
            // and we may continue and explore the edit operations of this graph
           // if (!it.isDoneEdge())
             //   abort();

            if( !it.isDoneVertex() || !it.isDoneEdge() )
            {
                // cout << __LINE__ << endl;
                iTotalGraphsExamined++;
                // Go through all possible vertex addition operations
                while( !it.isDoneVertex() )
                {

                    // cout << __LINE__ << endl;
                    EditOp vEdit = it.NextVertexOp();
                    if( kSum.find(vEdit) == kSum.end() )
                        kSum[vEdit] = 1;
                    else
                        kSum[vEdit]++;
                }

                // Go through all possible edge addition operations
                while( !it.isDoneEdge() )
                {

                    // cout << __LINE__ << endl;
                    //EEditOp eEdit = it.NextEdgeOp();
                    EditOp eEdit = it.NextEdgeOp();
                    if( kSum.find(eEdit) == kSum.end() )
                        kSum[eEdit] = 1;
                    else
                        kSum[eEdit]++;
                }

            } // End check for subgraph isomorphism

        } // End if exclude
    } // End for

    cout << "Examined: " << iTotalGraphsExamined << endl;
    cout << "kSum size: " << kSum.size() << endl;

    int iTotalEditSum = 0;
    for( map< EditOp, int >::iterator it=kSum.begin(); it != kSum.end(); ++it )
        iTotalEditSum += it->second;

    EditOpDist kResDist;

    if( bUnique )
    {



        Graph kTotalUnion;

        if( pUnion == 0 )
            kTotalUnion = GraphUnion(kVec);
        else
            kTotalUnion = *pUnion;


        vector< pair<string, double> > editStats;




        //-------------------------------------------------------
        // Check which was the best vertex edit op, and save how good it was
        for( map< EditOp, int >::iterator it=kSum.begin(); it != kSum.end(); ++it )
        {
            Graph vOpRes = ApplyEditOp(GP, it->first);

            //out <<  m_IDTypes[it->first.first] << ", " << m_IDTypes[it->first.second] << '\t' << ((double)it->second / (double)iTotalEditSum)  << endl;
            //stringstream sTmp; sTmp << m_IDTypes[it->first.first] << ", " << m_IDTypes[it->first.second];
            //editStats.push_back( make_pair(sTmp.str(), (double)it->second / (double)iTotalEditSum));


            // vEditOp.second, ID of the new vertex to connect to
            // vEditOp.first, ID of the existing vertex
            if( !IsSubgraphContained(vOpRes, kTotalUnion) )
            {
                //---------------------//
                // Make sure that the new graph union contains some new information
                vector<Graph> kTmpVec;
                if( pUnion == 0 )
                {
                    for(unsigned int j=0; j < kVec.size(); j++)
                        if( j != (unsigned int)iIndex )
                            kTmpVec.push_back(kVec[j]);
                }
                else
                    kTmpVec.push_back(kTotalUnion);
                // Also add what would be the result of this addition
                kTmpVec.push_back(vOpRes);
                Graph kUnion = GraphUnion(kTmpVec);
                if( !GraphEqual(G, kUnion) )
                {
                    //iVBest = it->second;
                    //kBest = it->first;
                    kResDist[it->first] = (double)it->second / (double)iTotalEditSum;
                }
                //---------------------//
            }
        }
        //-------------------------------------------------------

    }
    else
    {
        for( map< EditOp, int >::iterator it=kSum.begin(); it != kSum.end(); ++it )
        {
            kResDist[it->first] = (double)it->second / (double)iTotalEditSum;
        }
    }


    return kResDist;

}
//----------------------------------------------------------------
pair<bool, Vertex> GraphFunctions::FindVertex(unsigned int iName, const Graph& G)
{
    Iter_t vi, vi_end;
    // For each vertex
    for (tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
    {
        if( get(vertex_name, G, *vi) == iName )
            return make_pair(true, *vi);
    }

    return make_pair(false, Vertex());
}

//----------------------------------------------------------------
pair<bool, Edge> GraphFunctions::FindEdge(const Vertex v1,const Vertex v2,const Graph& G)
{
    graph_traits<Graph>::edge_iterator firstE, lastE;
    // For each vertex
    Edge e;
    for (tie(firstE, lastE) = edges(G); firstE != lastE; ++firstE)
    {
        // Get m_PG vertice pair for this edge
        Vertex u = source(*firstE, G);
        Vertex v = target(*firstE, G);
        if( (v1 == u && v2 == v) ||
                (v1 == v && v1 == u)){
            e = *firstE;
            return make_pair(true, e);
        }
    }
    return make_pair(false, e);
}

//----------------------------------------------------------------
std::pair<bool, std::vector< std::map<Vertex, Vertex> > >
GraphFunctions::IsSubgraphContained(const Graph& G1, const Graph& G2, bool bIsUnique, bool bAllMappings)
{
    std::vector< std::map<Vertex, Vertex> > kReturnMap;
    if( bIsUnique )
    {

        // Pointer to the smallest graph
        const Graph* pSG;
        const Graph* pLG;

        pSG = &G1;
        pLG = &G2;

        map<unsigned int, Vertex> kMap;

        // Check that all the vertices of the smallest graph and all the edges
        // are present in the bigger graph


        Iter_t vi, vi_end;
        Iter_t vi1, vi_end1;

        for (tie(vi, vi_end) = vertices(*pSG); vi != vi_end; ++vi)
        {
            bool bFound = false;
            // Check if we can find this vertex in the larger graph
            for (tie(vi1, vi_end1) = vertices(*pLG); vi1 != vi_end1; ++vi1)
            {
                if( get(vertex_name, *pSG, *vi) == get(vertex_name, *pLG, *vi1) )
                {
                    kMap[get(vertex_name, *pLG, *vi1)] = *vi1;
                    bFound = true;
                }
            }
            if(!bFound)
                make_pair(false, kReturnMap);
        }

        for (tie(vi, vi_end) = vertices(*pSG); vi != vi_end; ++vi)
        {
            for (tie(vi1, vi_end1) = vertices(*pSG); vi1 != vi_end1; ++vi1)
            {
                pair<Edge, bool> kRet1 = edge( *vi, *vi1, *pSG);
                pair<Edge, bool> kRet2 = edge( kMap[get(vertex_name, *pSG, *vi)], kMap[get(vertex_name, *pSG, *vi1)], *pLG);

                // If the edge exist in the smaller graph, it must also exist in the larger graph
                if( kRet1.second )
                    if( !kRet2.second )
                        make_pair(false, kReturnMap);
            }
        }

        return make_pair(true, kReturnMap);
    }
    else
    {
        // Run ullman on it

        VertexLabelPredicate alabel(G1,G2);
        trueEdgePredicate blabel;
        bool b1 = false;

        if( bAllMappings )
        {
            std::vector< vector<std::pair<Vertex,Vertex> > > mapping;
            b1 = ullmann_all(G1, G2, alabel, blabel, mapping);

            if(b1)
            {
                // Transform the mapping into the format map<Vertex, Vertex>
                // mapping from G1 to G2
                for(unsigned int i=0; i < mapping.size(); i++)
                {
                    map<Vertex, Vertex> kTmp;
                    for(unsigned int j=0;j < mapping[i].size(); j++)
                        kTmp[mapping[i][j].first]  = mapping[i][j].second;
                    kReturnMap.push_back(kTmp);
                }


            }
        }
        else
        {
            std::vector<std::pair<Vertex,Vertex> >     mapping;
            b1 = ullmann(G1, G2, alabel, blabel, mapping);
            // Transform the one existing mapping

            if( b1 )
            {
                map<Vertex, Vertex> kTmp;
                for(unsigned int j=0;j < mapping.size(); j++)
                    kTmp[mapping[j].first]  = mapping[j].second;
                kReturnMap.push_back(kTmp);
            }

        }
        return std::make_pair(b1, kReturnMap);
    }
}
//----------------------------------------------------------------
bool GraphFunctions::IsSubgraphContained(const Graph& G1, const Graph& G2, bool bIsUnique)
{
    // We are just interested in the boolean value if it is contained or not
    return IsSubgraphContained(G1, G2, bIsUnique, false).first;
}
//----------------------------------------------------------------
Graph GraphFunctions::GraphUnion( const vector<Graph>& kGraphs )
{
    list<const Graph*> kGraphsTmp;
    for( vector<Graph>::const_iterator it = kGraphs.begin(); it != kGraphs.end(); ++it )
        kGraphsTmp.push_back(&(*it));
    return GraphUnion(kGraphsTmp);
}
//----------------------------------------------------------------
Graph GraphFunctions::GraphUnion( list<Graph>& kGraphs )
{
    list<const Graph*> kGraphsTmp;
    for( list<Graph>::iterator it = kGraphs.begin(); it != kGraphs.end(); ++it )
        kGraphsTmp.push_back(&(*it));
    return GraphUnion(kGraphsTmp);
}
//----------------------------------------------------------------
Graph GraphFunctions::GraphUnion( list<const Graph*>& kGraphs )
{
    Graph kUnion;

    map<unsigned int, Vertex> vMap;

    for(list<const Graph*>::const_iterator it=kGraphs.begin(); it!=kGraphs.end(); ++it)
    {
        const Graph* G = *it;
        // 1. Add all those vertices which are not already in the union
        Iter_t vBegin, vEnd;
        for( tie(vBegin, vEnd) = vertices(*G); vBegin!=vEnd; ++vBegin )
        {
            int iId = get(vertex_name, *G, *vBegin);
            if( vMap.find(iId) == vMap.end() )
            {
                // Add it
                Vertex vNew = add_vertex(kUnion);
                //kUnion[vNew].sName = ((*G)[*vBegin]).sName;
                put(vertex_name, kUnion, vNew, iId);
                vMap[iId] = vNew;
            }
        }



        // 2. Add all the edges which are not already in the union
        graph_traits<Graph>::edge_iterator firstE, lastE;
        // For each edge
        for (tie(firstE, lastE) = edges(**it); firstE != lastE; ++firstE)
        {
            Vertex vSource = vMap[get(vertex_name, **it, source(*firstE, **it))];
            Vertex vTarget = vMap[get(vertex_name, **it, target(*firstE, **it))];

            pair<Edge, bool> kRet = edge( vSource, vTarget, kUnion);

            if( !kRet.second )
                // Add edge
                add_edge(vSource,vTarget, kUnion);
        }

    }

    return kUnion;
}
//----------------------------------------------------------------
Graph GraphFunctions::ApplyEditOp(const Graph& G, EditOp kEditOp, bool bUnique)
{
    // cout<< __FILE__ << ":" << __LINE__ << endl;
    pair<unsigned int, unsigned int> vEditOp = make_pair(kEditOp.get<1>(), kEditOp.get<2>());

    //   cout<< __FILE__ << ":" << __LINE__ << endl;
    if( kEditOp.get<0>() )
    {
        //    cout<< __FILE__ << ":" << __LINE__ << endl;
        // If it is a vertex addition
        Graph kRes = G;

        if (bUnique){
            Vertex vExisting;
            pair<bool,Vertex> kVRes = FindVertex(vEditOp.first, kRes);

            if( kVRes.first )
                vExisting = kVRes.second;

            Vertex vNew = add_vertex(kRes);
            put(vertex_name, kRes, vNew, vEditOp.second);


            if( kVRes.first )
                // Now add the edge as well
                add_edge(vExisting, vNew, kRes);
        }
        else {

            Vertex vNew = add_vertex(kRes);
            put(vertex_name, kRes, vNew, vEditOp.second);

            add_edge(vEditOp.first, vNew, kRes);
        }
        return kRes;
    }
    else
    {

        Graph kRes = G;
        if (bUnique){
            // If it is an edge addition
            Vertex v1 = FindVertex(vEditOp.first, kRes).second;
            Vertex v2 = FindVertex(vEditOp.second, kRes).second;

            // Now add the edge as well
            add_edge(v1, v2, kRes);
        }
        else {
            if( edge(vEditOp.first, vEditOp.second, G).second )
                cout << "Trying to add an edge that already exists!" << endl;
            add_edge(vEditOp.first, vEditOp.second, kRes);
        }

        return kRes;
    }
}
//----------------------------------------------------------------
bool GraphFunctions::GraphEqual(const Graph& G1, const Graph& G2, bool isUnique)
{
    if (isUnique){
        if( num_vertices(G1) != num_vertices(G2) )
            return false;
        if( num_edges(G1) != num_edges(G2) )
            return false;

        Iter_t G1begin, G1end; tie(G1begin, G1end) = vertices(G1);
        Iter_t G2begin, G2end; tie(G2begin, G2end) = vertices(G2);

        vector<Vertex> V1, V2;
        V1.resize(num_vertices(G1));
        V2.resize(num_vertices(G2));

        copy(G1begin, G1end, V1.begin());
        copy(G2begin, G2end, V2.begin());

        VertexSorter kSortG1(G1); VertexSorter kSortG2(G2);
        sort(V1.begin(), V1.end(), kSortG1);
        sort(V2.begin(), V2.end(), kSortG2);

        if( !std::equal(V1.begin(), V1.end(), V2.begin()) )
            return false;

        graph_traits<Graph>::edge_iterator G1Ebegin, G1Eend, G2Ebegin, G2Eend;
        tie(G1Ebegin, G1Eend) = edges(G1); tie(G2Ebegin, G2Eend) = edges(G2);

        for( tie(G1Ebegin, G1Eend) = edges(G1); G1Ebegin != G1Eend; ++G1Ebegin )
        {
            Vertex u = FindVertex(get(vertex_name, G1, source(*G1Ebegin, G1)), G2).second;
            Vertex v = FindVertex(get(vertex_name, G1, target(*G1Ebegin, G1)), G2).second;
            if( !edge(u, v, G2).second )
                return false;
        }

        return true;
    }
    else {
        return isomorphism(G1,G2);
    }
}
//----------------------------------------------------------------
void GraphFunctions::SaveGraph(string sFilename, const Graph& G, vector<const Graph*> pOverlay, const GraphDatabase* pD)
{


    // Save the graph to the file
    std::ofstream ofs( sFilename.c_str() );
    if( pOverlay.size() == 0)
    {
        // Create the vertex and edge writers
        Vertex_writer vertexwriter(G, pD);

        boost::write_graphviz(ofs, G, vertexwriter );
    }
    else
    {
        // Create the vertex and edge writers
        Vertex_writer vertexwriter(G, pD, pOverlay);
        Edge_writer<Graph> edgewriter(G, pOverlay);

        boost::write_graphviz(ofs, G, vertexwriter, edgewriter );

    }
    ofs.close();
    system(("neato -Tpng -Gcharset=latin1 " + sFilename + " > " + sFilename + ".png").c_str());
}



void GraphFunctions::SaveGraphToFile(string sfilename, const Graph& g, const GraphDatabase& D){
    std::ofstream out(sfilename.c_str() );

    out << "graph TopoGraph {" << endl;
    out << "overlap = false; splines=true;" << endl;
    BGL_FORALL_VERTICES(v, g, Graph){
        out << v << " [shape=ellipse" << " label=\"S" << v << "_" << D.GetStringFromVertexID(get(vertex_name,g,v)) << "\"];" << std::endl;
    }


    BGL_FORALL_EDGES(e, g, Graph){
        out << source(e, g) << " -- " << target(e, g) << ";" << std::endl; cout.flush();
    }
    out <<"}";
    out.close();
    system(("neato -Tpng -Gcharset=latin1 " + sfilename + " > " + sfilename + ".png").c_str());
}


void  GraphFunctions::SaveOverlayGraphToFile(std::string sfilename, const Graph& mainGraph, const Graph& inputGraph, const Graph& editedGraph, const GraphDatabase& D){
    VertexLabelPredicate alabel(inputGraph, mainGraph);
    trueEdgePredicate blabel;
    vector<std::pair<Vertex,Vertex> >  mapping;
    ullmann(inputGraph, mainGraph, alabel, blabel, mapping);

    // Transform the mapping into the format map<Vertex, Vertex>
    // mapping from G1 to G2

    map<Vertex, Vertex> kTmpMain, kTmpInput;
    set<Vertex> mainVertices;
    set<Vertex> inputVertices;
    for(unsigned int j=0;j < mapping.size(); j++){
        kTmpMain[mapping[j].first]  = mapping[j].second;
        kTmpInput[mapping[j].second] = mapping[j].first;
        mainVertices.insert(mapping[j].second);
        inputVertices.insert(mapping[j].first);
    }


    map<Vertex, Vertex> kTmpEdited, kTmpInputtoEdited;
    VertexLabelPredicate alabel1(inputGraph, editedGraph);
    trueEdgePredicate blabel1;
    vector<std::pair<Vertex,Vertex> >  mapping1;
    ullmann(inputGraph, editedGraph, alabel1, blabel1, mapping1);

    for(unsigned int j=0;j < mapping1.size(); j++){
        kTmpInputtoEdited[mapping1[j].first]  = mapping1[j].second;
        kTmpEdited[mapping1[j].second] = mapping1[j].first;
    }

    unsigned char R = 0, G = 0, B = 255, A = 255;

    std::ofstream out(sfilename.c_str() );

    out << "graph TopoGraph {" << endl;
    out << "overlap = false; splines=true;" << endl;
    BGL_FORALL_VERTICES(v, mainGraph, Graph){
        if (mainVertices.find(v) != mainVertices.end())
            out << v << " [shape=ellipse" << " label=\"S" << v << "_" << D.GetStringFromVertexID(get(vertex_name,mainGraph,v)) << "\"" <<
                   " color=\"blue\"];" << std::endl;
        else
            out << v << " [shape=ellipse" << " label=\"S" << v << "_" << D.GetStringFromVertexID(get(vertex_name,mainGraph,v)) << "\"];" << std::endl;

    }

    BGL_FORALL_EDGES(e, mainGraph, Graph){
        if (mainVertices.find(source(e, mainGraph)) != mainVertices.end() && mainVertices.find(target(e, mainGraph)) != mainVertices.end())
           out << source(e, mainGraph) << " -- " << target(e, mainGraph) << " [color=\"blue\"];" << std::endl;
        else
           out << source(e, mainGraph) << " -- " << target(e, mainGraph) << ";" << std::endl;
    }

    // now add the edited graph
    Vertex missingVertex = -1;
    BGL_FORALL_VERTICES(v, editedGraph, Graph){
        if (kTmpEdited.find(v) == kTmpEdited.end()){
            out << "F" << v << " [shape=square" << " label=\"F" << v << "_" << D.GetStringFromVertexID(get(vertex_name,editedGraph,v)) << "\"" <<
                   " color=\"red\"];" << std::endl;
            missingVertex = v;
        }
    }

    // the edges
    if (missingVertex != -1){
        BGL_FORALL_OUTEDGES(missingVertex, e, editedGraph, Graph){
                out << "F" << (int)missingVertex << " -- " << kTmpMain[kTmpEdited[target(e, editedGraph)]]  <<
                      " [color=\"red\"];" << std::endl;
        }
    }
    else{
        BGL_FORALL_EDGES(e, editedGraph, Graph){

            if (inputVertices.find(kTmpEdited[source(e, editedGraph)]) != inputVertices.end()
                    && inputVertices.find(kTmpEdited[target(e, editedGraph)]) != inputVertices.end() ){

                Vertex inputSource = kTmpEdited[source(e, editedGraph)];
                Vertex inputTarget = kTmpEdited[target(e, editedGraph)];
                Vertex mainSource = kTmpMain[inputSource];
                Vertex mainTarget = kTmpMain[inputTarget];

                if (!edge(mainSource,mainTarget,mainGraph).second){
                    out << mainSource << " -- " << mainTarget  <<
                           " [color=\"red\"];" << std::endl;
                }
            }
        }
    }

    out <<"}";

    out.close();
    system(("neato -Tpng -Gcharset=latin1 " + sfilename + " > " + sfilename + ".png").c_str());

}

//----------------------------------------------------------------
void GraphFunctions::SaveGraph(string sFilename, const Graph& G,const GraphDatabase* pD, const Graph* pOverlay)
{
    vector<const Graph*> kTmp;
    if( pOverlay )
        kTmp.push_back(pOverlay);
    SaveGraph(sFilename, G, kTmp, pD);
}
//----------------------------------------------------------------
// Removes those vertices which have no edges
void GraphFunctions::RemoveIsolatedVertices(Graph* pG)
{

    Graph kFinalGraph;
    Iter_t vi, vi_end;
    graph_traits<Graph>::edge_iterator firstE, lastE;

    Graph& G = *pG;

    // Maintain a mapping from the old vertex descriptor -> new descriptor
    map< Vertex, Vertex*> tmpMapping;
    //out_edges(v, g)
    for (tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
    {
        tmpMapping[*vi] = 0;
        bool bC; bC = true;

        if( out_degree(*vi, G) == 1 )
        {
            boost::graph_traits<Graph>::out_edge_iterator e, e_end;

            tie(e, e_end) = out_edges(*vi, G);
            //get(property, g, x)
            if( get(vertex_name, G, target(*e, G)) == get(vertex_name, G, *vi))
                bC = false;
        }


        // Only add if this vertex has some edges, and if that connection is not to itself only.
        if( out_degree(*vi, G) != 0 && bC )
            //&& !(   out_degree(*vi, G) == 1 &&  (target(*out_edges(*vi, G).first, G)==(*vi))   ))
        {
            // Add it
            Vertex* kV = new Vertex(add_vertex(kFinalGraph));
            //kFinalGraph[*kV] = G[*vi];
            int iID = get(vertex_name, G, *vi);

            put(vertex_name, kFinalGraph, *kV, iID);

            tmpMapping[*vi] = kV;
        }
    }


    // Transfer all edges
    for (tie(firstE, lastE) = edges(G); firstE != lastE; ++firstE)
        if( tmpMapping[source(*firstE, G)] != 0 && tmpMapping[target(*firstE, G)] != 0  )
            add_edge(*tmpMapping[source(*firstE, G)], *tmpMapping[target(*firstE, G)], kFinalGraph);

    for(map<Vertex, Vertex*>::const_iterator i = tmpMapping.begin(); i != tmpMapping.end(); ++i)
        delete i->second;

    set_property(kFinalGraph, boost::graph_name, get_property(G,boost::graph_name));
    G = kFinalGraph;
}
//----------------------------------------------------------------
void GraphFunctions::PrintEditOp(const Graph& G, EditOp& kOp, const GraphDatabase& D)
{
    unsigned int newcat;
    if (kOp.get<0>()){
        newcat = kOp.get<2>();
        if( !D.IsUnique() )
            cout << "Vertex operation to between (" << D.GetStringFromVertexID(get(vertex_name, G, kOp.get<1>()));
        //else
        //    cout << "Vertex operation to between (" << D.GetStringFromVertexID(get(vertex_name, G, kOp.get<1>()));
    }
    else {
        newcat = get(vertex_name, G, kOp.get<2>());
        cout << "Edge operation to between (" << D.GetStringFromVertexID(get(vertex_name, G, kOp.get<1>()));
    }
    cout << "," << D.GetStringFromVertexID(newcat) << ")" << endl;

}
//----------------------------------------------------------------
void GraphFunctions::PrintEditOp(const Graph& G, EditOp& kOp)
{
    unsigned int newcat;
    if (kOp.get<0>()){
        newcat = kOp.get<2>();
        cout << "Vertex operation to between (" << get(vertex_name, G, kOp.get<1>());
    }
    else {
        newcat = get(vertex_name, G, kOp.get<2>());
        cout << "Edge operation to between (" << get(vertex_name, G, kOp.get<1>());
    }
    cout << "," << newcat << ")" << endl;

}
//----------------------------------------------------------------
void GraphFunctions::SaveVectorOfGraphs(const GraphDatabase& D, string sDir, const vector<Graph>& kVec, int iMax)
{
    stringstream f, run;
    // Save all FSGs 1-100
    for(unsigned int i=0; i < min(iMax, (int)kVec.size()); i++)
    {
        f << sDir << "/" << i << ".dot";
        cout << f.str() << endl;
        GraphFunctions::SaveGraphToFile(f.str(), kVec[i], D);

        stringstream run;

        run << "dot -Tpng " << f.str() << " -o " << f.str() << ".png";
        cout << run.str() << endl;
        system (run.str().c_str());

        run.str("");
        f.str("");

    }

}
//----------------------------------------------------------------
std::pair<ClusteringMap, float> GraphFunctions::CalculateClusterCoeff(const Graph& G)
{
    ClusteringContainer coefs(num_vertices(G));
    ClusteringMap cm(coefs, G);
    float cc = all_clustering_coefficients(G, cm);
    return make_pair(cm, cc);
}

//----------------------------------------------------------------
pair<float, int> GraphFunctions::GetCharacteristicPathLengthDiameter(const Graph& G)
{
        int V = num_vertices(G);


         vector<vector<int> > D(V, vector<int>(V));


        // Create an edge weight map and init it to all 1's
        std::map<Edge, int> ktmp;
        boost::associative_property_map< std::map<Edge, int> >
            kWeightMap1(ktmp);
        graph_traits<Graph>::edge_iterator firstE, lastE;
        for (tie(firstE, lastE) = edges(G); firstE != lastE; ++firstE)
            ktmp.insert(make_pair(*firstE, 1));

        johnson_all_pairs_shortest_paths(G, D, get(vertex_index, G), kWeightMap1, 0);
        //johnson_all_pairs_shortest_paths(m_Graphs[i], D, boost::distance_map(&d[0]));

        int iSum = 0;
        int iDiam = 0;
        int iTotalCombs = 0;
        for(int j =0; j < V; j++)
            for(int k=j; k < V; k++)
            {
                iSum += D[j][k];
                iTotalCombs++;
                if( D[j][k] > iDiam )
                    iDiam = D[j][k];
            }
        return make_pair(((float)iSum / (float)iTotalCombs), iDiam);
}
//----------------------------------------------------------------
int GraphFunctions::GetNumOfVerticesOfCategory(const Graph& G, std::set<std::string> sSet, const GraphDatabase& D)
{
    Iter_t vi, vi_end;
    int iRes = 0;
    // For each vertex
    for (tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
    {
        if( sSet.find(D.GetStringFromVertexID(get(vertex_name, G, *vi))) != sSet.end() )
            iRes++;
    }
    return iRes;
}
//----------------------------------------------------------------
bool GraphFunctions::SaveGraphToXML(std::string XMLfilename, const Graph& G, const GraphDatabase& D){


    QFile file(XMLfilename.c_str());
    if (!file.open(QIODevice::WriteOnly))
    {
        printf("The file is in read only mode \n");
        return false;
    }
    else
    {
        QXmlStreamWriter* xmlWriter = new QXmlStreamWriter();
        xmlWriter->setDevice(&file);
        xmlWriter->setAutoFormatting(true);


        xmlWriter->writeStartDocument();

        /* Open floor tag */
        xmlWriter->writeStartElement("MITquest");

        /* Now write spaces one by one */
        BGL_FORALL_VERTICES(v, G, Graph){
            xmlWriter->writeStartElement("space");
            xmlWriter->writeAttribute(QString("name"), QString("%1").arg(v));
            xmlWriter->writeAttribute(QString("type"),  QString( D.GetStringFromVertexID(get(vertex_name, G, v) ).c_str()));

            BGL_FORALL_OUTEDGES(v, e, G, Graph) {
                xmlWriter->writeStartElement("portal");
                xmlWriter->writeAttribute(QString("target"), QString("%1").arg(target(e, G)));
                // std::cout << source(e, g) << " -> " << target(e, g) << std::endl; cout.flush();
                // std::cout << g.graph()[source(e, g)].category << " -> " << target(e, g) << std::endl; cout.flush();
                xmlWriter->writeEndElement();
            }

            xmlWriter->writeEndElement();
        }
        xmlWriter->writeEndElement();

        xmlWriter->writeEndDocument();
        delete xmlWriter;

        file.close();
        return true;

    }
}

GraphDatabase GraphFunctions::ExtractSegments(GraphDatabase& D, std::string path, CategoryDegreeDist dist,
                                              double centralNodenessThreshold, bool bGraphWise, int minSegmentedGraphSize ){


    set<int> freq;
    // First determine the vertices that are average degree > threshold
    vector<Graph> graphs;
    vector<string> sFilenames;
    GraphDatabase retGraph;
    CategoryDegreeDist::iterator it;

    if( dist.size() == 0 )
        cout << "WARNING 0 DEGREE DIST SIZE IN EXTRACT SEGMENTS!" << endl;

    if( !bGraphWise )
    {
        for (it = dist.begin(); it != dist.end(); ++it){
            double dSum = 0.0;
            vector<double> vDist = it->second;
            for(int i=0; i < vDist.size(); i++)
                dSum += (double)i * vDist[i];
                /*
            cout << dSum << endl;
            cout << D.GetStringFromVertexID(it->first) << "," << it->first << endl;
            cout << D.GetVertexIDFromString(D.GetStringFromVertexID(it->first)) << endl;*/
            if (dSum >= centralNodenessThreshold){
                freq.insert(it->first);
                cout << "Including category: " << D.GetStringFromVertexID(it->first) << endl;
            }
        }
    }

    for (unsigned int i =0; i < D.GetNumGraphs(); i++){
        Graph G0 = D.GetGraph(i);
        string str = D.GetGraphFilenameVector()[i];
        string str2 = "corpus//";
        string str3 = str;
        if( str.find(str2) != string::npos )
            str3 = str.replace(str.find(str2),str2.length(), "");
        vector<Graph> ret = D.SegmentGraph(G0,freq, centralNodenessThreshold);
        for(int j=0; j < ret.size(); j++)
        {

            stringstream sTmp; sTmp << D.m_kLoader.m_GraphFilenames[i];
            sTmp << "_" << j;
            graphs.push_back(ret[j]);
            sFilenames.push_back(sTmp.str());
        }

        /*
        for (int j =0; j<ret.size(); j++){
            if (num_vertices(ret[j]) < minSegmentedGraphSize) continue;

            char buf[32];
            char filename[32];
            sprintf(buf, "%s/%s_%d", path.c_str(), str3.c_str(),j);
            sprintf(filename, "%s_%d", str3.c_str(),j);
            cout << "saving " << buf << endl;
          //  GraphFunctions::SaveGraphToFile(string(buf) + ".dot",ret[j], D);
            if (!GraphFunctions::SaveGraphToXML(string(buf) + ".xml",ret[j], D)){
                cout << "Cannot save file at " << buf << " . Returning an empty database" << endl;
                return GraphDatabase();
            }
            graphs.push_back(ret[j]);
            retGraph.m_kLoader.m_GraphFilenames.push_back(string(filename));
        }*/
    }

    //int numberOfGraphs = retGraph.LoadAllGraphs(path,-1,false);

    //cout << "Loaded " << numberOfGraphs << " graphs." << endl;;
    retGraph.SetGraphVector(graphs);
//
    retGraph.m_kLoader.m_Types = D.m_kLoader.m_Types;
    retGraph.m_kLoader.m_IDTypes = D.m_kLoader.m_IDTypes;
    retGraph.m_kLoader.m_TypesID = D.m_kLoader.m_TypesID;
    retGraph.m_kLoader.m_iIDCounter = D.m_kLoader.m_iIDCounter;
    retGraph.m_kLoader.m_GraphFilenames = sFilenames;
    retGraph.m_bUnique = D.m_bUnique;

    return retGraph;
}


vector<FrequentSubgraph> GraphFunctions::GetClosedFrequentSubgraphs(const vector<FrequentSubgraph>& kFSGs)
{
    vector<FrequentSubgraph> kAdded;
    // Transform all the frequent subgraphs into a closed form
    for(int i=0; i < kFSGs.size(); i++)
    {
        // Go through all the already added, if one of them is contained in this one then
        // remove it

        // Only add if this one is not contained in any of the other already added
        bool bAdd = true;
        for(int j=0; j < kAdded.size(); j++)
        {
            if( IsSubgraphContained(kFSGs[i].G, kAdded[j].G, false) )
            {
                // So this one is already contained in one of the added
                bAdd = false;
                break;
            }
        }

        if( bAdd )
        {

            // Remove all of those which are contained in this one
            for(int j=0; j < kAdded.size(); j++)
            {
                // If kAdded[j] is contained in the one we're adding, remove it
                if( IsSubgraphContained(kAdded[j].G, kFSGs[i].G,  false) )
                {
                    kAdded.erase(kAdded.begin() + j);
                }
            }
            kAdded.push_back(kFSGs[i]);
        }
    }

    return kAdded;
}
